class Solution {
    vector<string> result;
    int poingNum = 0;

    bool isValid(const string& s, int begin, int end)
    {
        if (begin > end) return false;
        if (s[begin] == '0' && begin != end) return false;

        int num = 0;
        for (int i = begin; i <= end; ++i)
        {
            if (!isdigit(s[i])) return false;
            num = num * 10 + (s[i] - '0');//**********
            if (num > 255) return false;
        }
        return true;
    }
    void backTracking(string& s, int startIndex)
    {
        if (poingNum == 3)
        {
            if (isValid(s, startIndex, s.size() - 1))
                result.push_back(s);
            return;
        }
        for (int i = startIndex; i < s.size(); ++i)
        {
            if (isValid(s, startIndex, i))
            {
                s.insert(s.begin() + i + 1, '.');
                ++poingNum;
                backTracking(s, i + 2);
                s.erase(s.begin() + i + 1);
                --poingNum;
            }
            else break;
        }
    }
public:
    vector<string> restoreIpAddresses(string s) {
        backTracking(s, 0);
        return result;
    }
};